import java.util.LinkedList;
import java.util.Queue;

public class CheckCompletenessBinaryTree {
    public boolean isCompleteTree1(TreeNode root) {
        // bfs
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                // 遇到 null 就停止入队
                break;
            }
        }

        // 如果是完全二叉树, 那么队列里面就应该全部都是 null
        while(!queue.isEmpty()) {
            if(queue.poll() != null) {
                // 出现 非null 节点说明不是完全二叉树
                return false;
            }
        }

        return true;
    }


//    public boolean isCompleteTree(TreeNode root) {
//        List<Pair<TreeNode, Integer>> list = new ArrayList<>();
//        list.add(new Pair<>(root, 0));
//
//        int i = 0;
//        while(i < list.size()) {
//            Pair<TreeNode, Integer> pair = list.get(i++);
//            TreeNode node = pair.getKey();
//            int index = pair.getValue();
//            // 将包括叶节点的左右 null 节点也算进来
//            if(node != null) {
//                list.add(new Pair<>(node.left, 2 * index + 1));
//                list.add(new Pair<>(node.right, 2 * index + 2));
//            }
//        }
//
//        // 拿到最后一个节点的下标, 和总结点数相比较, 如果条件不满足, 说明不是完全二叉树
//        return list.get(i-1).getValue() == list.size() - 1;
//    }
}
